1. Field of the Invention
The present invention generally relates to data processing, and more particularly to a data processing method having the function of checking how many bits indicating a predetermined value are contained in data consisting of a plurality of bits and performing a predetermined bit operation on such data. Further, the present invention is concerned with a device using the above data processing method. The present invention is suitable particularly for data liable to be affected by the performance of a storage medium or noise. For example, the present invention can be suitably applied to an electronic device having an erasable and programmable memory such as a flash memory.
2. Description of the Prior Art
Recently, erasable and programmable memories such as flash memories have been widely used in various electronic devices. The flash memories do not need a backup source and data stored therein is electrically erasable and programmable. However, the flash memories have a disadvantage in that data can be erased only a limited number of times. If data stored in a flash memory is erased an excessive number of times, a bit is fixed at a low or a high level and cannot be changed.
As another aspect of the flash memory, the data erasing operation on the flash memory is performed so that the data erasing unit, in which data is erased at one time, is equal to a few kbytes to a few hundreds of kbytes. This means that the data erasing operation cannot be performed for every byte. In a flash memory divided into blocks, each of which is divided into sectors, if data stored in a block or a sector of the flash memory becomes unnecessary, an erasable-state flag for the above block or sector is turned ON and all data stored therein is erased, thereby to get ready for writing. Normally, erasable-state flags and fault flags are provided for blocks and sectors of the flash memory. The erase flags indicate whether or not data stored in the respective blocks or sectors are erasable. The fault flags indicate whether or not the respective blocks or sectors are faulty. However, there is a possibility that the flash memory will become faulty if data is erased therefrom an excessive number of times. This means that areas storing the flags may become faulty when flag data is erased an excessive number of times. For this reason, redundant flag data is provided for the regular flag data.
FIG. 1 is a block diagram of a flash memory system, which is made up of a plurality of flash memories 11-1 through 11-n, a controller LSI (Large Scale Integrated circuit) device 12, a CPU (Central Processing Unit) 13 and an SRAM (Static Random Access Memory) 14. The controller LSI device 12 controls a data erasing and writing operation on the flash memories 11-1 through 11-n. The SRAM device 14 stores data to be written into the flash memories 11-1 through 11-n and data to be saved. The CPU 13 controls the operation of the overall flash memory system. Further, each of the flash memories 11-1 through 11-n has a flag storage area 11a in which an erasable-state flag, a fault flag and other predetermined flags are stored in the redundant formation.
When a decision on the flags including the redundant bit(s) is made, as shown in FIG. 2, a flag decision unit 15 formed by the CPU 13 makes a majority decision on the flags stored in the flag area 11a by counting the number of flag bits indicating "1" and/or the number of flag bits indicating "0".
Normally, data consisting of a plurality of bits, such as flag data as described above, is processed in the following ways.
FIGS. 3 and 4 show a first conventional data processing method for changing the lowest bit of N-bit data among bits indicating "1" to "0". The N-bit data processed in FIGS. 3 and 4 is four-bit data (1100).sub.2 (N=4) where the suffix 2 indicates the binary notation. FIG. 3 is a flowchart of the first conventional data processing method, and FIG. 4 shows how data is processed in each step. Steps S1 through S5 shown in FIG. 3 correspond to steps S1 through S5 shown in FIG. 4, respectively.
In step S1, binary data (0001).sub.2 is stored in a work area. In step S2, it is determined whether or not the data being processed is zero. When the result of this step is YES, the process is ended. When it is determined that the data is not zero, it is determined in step S3 whether or not the result (resultant data) of an AND logic operation on the bits of the data (1100).sub.2 and the work data (0001).sub.2 is zero. When the result of this determination is YES, the work data stored in the work area is shifted leftward by one bit in step S4, and the process returns to step S3. The above process is repeatedly performed until it is determined in step S3 that the result of the AND logic operation on the data (1100).sub.2 and the work is not zero. At this time, the process proceeds with step S5 in which an exclusive-OR operation on the data (1100).sub.2 and the work data is calculated and the result thereof is output as the processing result.
By the above-mentioned method, the work data becomes (0100).sub.2 after step S3 is performed three times, and the result of the step S3 decision does not become zero. The result of the exclusive-OR operation on the work data (0100).sub.2 and data (1100).sub.2 becomes (000).sub.2, in which the lowest bit of the four-bit data among the bits indicating "1" is changed to "0". The method shown in FIG. 3 needs the repetitive process performed i times (n .ltoreq.i.ltoreq.N) in order to change the lowest bit (n) indicating "1" of the N-bit data to "0".
FIGS. 5 and 6 show a second conventional data processing method for counting the number of "1" bits contained in N-bit data, which is four-bit data (1001).sub.2 in the case shown in FIGS. 5 and 6. FIG. 5 is a flowchart of the second conventional data processing method, and FIG. 6 shows how data is processed in each step. Steps S1-S5 shown in FIG. 5 correspond to steps S1-S5 shown in FIG. 6, respectively.
In step S1 shown in FIGS. 5 and 6, a variable indicating the number of "0" bits is reset to zero in step S1, and it is determined in step S2 whether or not the data being processed is zero. When the data is zero, the process is ended. When it is determined in step S2 that the data is not zero, the process proceeds with step S3 in which it is determined whether or not the result of an AND logic operation is performed on the data being processed and "01h" is 1. When it is determined in step S3 that the result of the AND logic operation is not 1, the process proceeds with step S5. When it is determined in step S3 that the result of the AND logic operation on the data and data "01h" is 1, the process proceeds with step S4 in which the variable is updated by adding 1 to the current value thereof. Then, step S5 is executed in which the data is shifted rightward by one bit. When the data being processed becomes zero, the process is ended.
The above process is repeatedly performed. When step S2 is executed five times as shown in FIG. 6, the data becomes zero, and the number of "1" bits contained in the data can be obtained. In the example being considered, two bits "1" are contained in the data. The method shown in FIG. 5 needs the repetitive process that is performed i times (n.ltoreq.i.ltoreq.N) in order to count the number (n) of "1" bits contained in the N-bit data.
FIGS. 7 and 8 show a third conventional data processing method for determining whether or not the number of bits indicating "1" contained in N-bit data is equal to or greater than m. The N-bit data processed in FIGS. 7 and 8 is four-bit data (1001).sub.2 (N =4) and m=3. FIG. 7 is a flowchart of the third conventional data processing method, and FIG. 8 shows how data is processed in each step. Steps S1 through S5 shown in FIG. 7 are the same as corresponding steps shown in FIG. 5, and step S6 shown in FIG. 7 determines whether or not the number of "1" bits obtained in step S4 is equal to or greater than m. The third conventional data processing method needs the repetitive process that is performed i times (n.ltoreq.i.ltoreq.N) in order to determine whether or not the number (n) of "1" contained in the N-bit data is equal to or greater than m.
FIGS. 9 and 10 show a fourth conventional data processing method for determining whether or not the number of bits indicating "1" contained in N-bit data is equal to or less than m. The N-bit data processed in FIGS. 9 and 10 is four-bit data (1001).sub.2 (N=4) and m=3. FIG. 9 is a flowchart of the fourth conventional data processing method and FIG. 10 shows how data is processed in each step. Steps S1 through S6 shown in FIG. 9 are the same as steps S1 through S6 shown in FIG. 10. Further, the steps S1 through S5 shown in FIG. 9 are the same as those corresponding steps shown in FIG. 7, and step S6 shown in FIG. 9 is different from that shown in FIG. 7. The fourth conventional data processing method needs the repetitive process that is performed i times (n.ltoreq.i.ltoreq.N) in order to determine whether or not the number (n) of "1" bits contained in the N-bit data is equal to or less than m.
FIGS. 11 and 12 show a fifth conventional data processing method for changing the lowest bit of N-bit data, among bits indicating "0", to "1". The N-bit data shown in FIGS. 11 and 12 is four-bit data (0011).sub.2 (N=4). FIG. 11 is a flowchart of the fifth conventional data processing method and FIG. 12 shows how data is processed in each step. Steps S1 through S5 shown in FIG. 11 correspond to steps S1 through S5 shown in FIG. 12.
The fifth conventional data processing method is obtained by modifying the aforementioned first data processing method shown in FIGS. 3 and 4 as follows. That is, step S2 shown in FIGS. 3 and 4 is modified so that the value to be compared is changed from "0" to "1", and the process in step S3 shown in FIGS. 3 and 4 is changed so that an OR logic operation on the data being processed and the work data is executed. Further, the process is modified that it proceeds with step S5 when it is determined in step S3 that the data is equal to the work data and it proceeds with step S4 when it is determined that the data is not equal to the work data. The other steps shown in FIGS. 11 and 12 are the same as those corresponding steps shown in FIGS. 3 and 4. The fifth conventional data processing method needs the repetitive process that is performed i times (n.ltoreq.i.ltoreq.N) in order to change the lowest bit of the N-bit data among bits indicating "0" to "1".
FIGS. 13 and 14 show a sixth conventional data processing method for counting the number of "0" contained in N-bit data, which is four-bit data (1001).sub.2 in the case shown in FIGS. 13 and 14. FIG. 13 is a flowchart of the sixth conventional data processing method, and FIG. 14 shows how data is processed in each step. Steps S1-S5 shown in FIG. 13 correspond to steps S1-S5 shown in FIG. 14, respectively.
The sixth conventional data processing method is obtained by modifying the aforementioned second data processing method shown in FIGS. 5 and 6 as follows. That is, step S2 shown in FIGS. 5 and 6 is modified so that the value to be compared is changed from "0" to "1", and the value to be compared in step S3 is changed to "0". Further, in step S5 shown in FIG. 13, the data is shifted rightward, and "1" is set to the highest (most significant) bit. The other steps shown in FIGS. 13 and 14 are the same as those corresponding steps shown in FIGS. 5 and 6. The sixth conventional data processing method needs the repetitive process that is performed i times (n.ltoreq.i.ltoreq.N) in order to count the number of bits indicating "0".
FIGS. 15 and 16 show a seventh conventional data processing method for determining whether or not the number of bits indicating "0" contained in N-bit data is equal to or greater than m. The N-bit data is four-bit data (1001).sub.2 in the case shown in FIGS. 15 and 16. FIG. 15 is a flowchart of the seventh conventional data processing method, and FIG. 16 shows how data is processed in each step. Steps S1-S6 shown in FIG. 15 correspond to steps S1-S6 shown in FIG. 16, respectively.
The steps S1 through S5 of the seventh conventional data processing method are the same as those corresponding steps of the above-mentioned sixth embodiment. In step S6 shown in FIG. 15, it is determined that the number of bits indicating "0" obtained in step S4 is equal to or greater than m. The seventh conventional data processing method needs the repetitive process that is performed i times (n.ltoreq.i.ltoreq.N) in order to determine whether or not the number of bits indicating "0" is equal to or greater than m.
FIGS. 17 and 18 show an eighth conventional data processing method for determining whether or not the number of bits indicating "0", contained in N-bit data, is equal to or less than m. The N-bit data is four-bit data (1001).sub.2 in the case shown in FIGS. 17 and 18. FIG. 17 is a flowchart of the seventh conventional data processing method, and FIG. 18 shows how data is processed in each step. Steps S1-S6 shown in FIG. 17 correspond to steps S1-S6 shown in FIG. 18, respectively.
The steps S1 through S5 of the eighth conventional data processing method are the same as corresponding those of the above-mentioned sixth embodiment. In step S6 shown in FIG. 17, it is determined that the number of bits indicating "0" obtained in step S4 is equal to or less than m. The eighth conventional data processing method needs the repetitive process that is performed i times (n.ltoreq.i.ltoreq.N) in order to determine whether or not the number of bits indicating "0" is equal to or less than m.
As described above, the conventional data processing methods have a disadvantage in that the loop processes must be repeatedly executed in order to invert the value of a desired bit of N-bit data and count the number of bits contained therein. Further, the number of times that the loop processes are executed increases as the number of bits forming data to be processed increases. Hence, the conventional data processing methods need a long time to obtain the operation results and do not have high efficiency in data processing devices such as flash memory systems.